public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().numDistinct1("rabbbit", "rabbit"));
        System.out.println(new Solution().numDistinct1("babgbag", "bag"));
    }
}

class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[t.length() + 1][s.length() + 1];
        for (int i = 0; i <= s.length(); i++) {
            dp[0][i] = 1;
        }
        //横竖两种循环方式皆可
        for (int i = 1; i <= t.length(); i++) {
            char ts = t.charAt(i - 1);
            for (int j = 1; j <= s.length(); j++) {
                char cs = s.charAt(j - 1);
                dp[i][j] = dp[i][j - 1];
                if (cs == ts) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
                dp[i][j] %= 1000000000 + 7;
            }
        }
        return dp[t.length()][s.length()];
    }

    //dp仅申请一维数组
    public int numDistinct1(String s, String t) {
        int[] dp = new int[s.length() + 1];
        for (int i = 0; i <= s.length(); i++) {
            dp[i] = 1;
        }

        for (int i = 1; i <= t.length(); i++) {
            char ts = t.charAt(i - 1);
            int[] dpTemp = new int[s.length() + 1];
            for (int j = 1; j <= s.length(); j++) {
                char cs = s.charAt(j - 1);
                dpTemp[j] = dpTemp[j - 1];
                if (cs == ts) {
                    dpTemp[j] += dp[j - 1];
                }
                dpTemp[j] %= 1000000000 + 7;
            }
            dp = dpTemp;
        }
        return dp[s.length()];
    }
}